package top.humbleyuan.stack;

import java.util.Stack;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 16:35
 * @Des 最长有效括号
 * @pro 待补充DP解法
 */
public class LeetCode_32 {
    public static void main(String[] args) {
        String s = "(())(";

        if(s == null || s.length() == 0) {
            System.out.println(0);
        }

        /**
         打断条件：stack is empty && s[i] == ')'
         **/

        int i = 0;
        int maxCount = 0;
        Stack<Integer> stack = new Stack<>();

        // -1进栈,做全体规则的计算
        stack.push(-1);
        while(i < s.length()) {
            if(s.charAt(i) == '(') {
                stack.push(i);
            } else {
                // 先弹出
                stack.pop();

                // 计算增加大小
                if(stack.empty()) {
                    // 空则中断,压入新起点做计算。相当于-1
                    stack.push(i);
                } else {
                    maxCount = Math.max(maxCount, i - stack.peek());
                }
            }

            i++;
        }

        System.out.println(maxCount);
    }
}
